package com.gitee.wsl.struct.tree.sample.trie
//
//import com.gitee.wsl.func.predicate.Predicate
//import kotlin.math.min
//
//
///**
// * A `bit-mapped trie` is a very wide and shallow tree (for integer indices the depth will be `≤6`).
// * Each node has a maximum of `32` children (configurable).
// * Access to a given position is done by converting the index to a base 32 number and using each digit to descend down the tree.
// * Modifying the tree is done similarly, but along the way the path is copied, returning a new root every time.
// * `Append` inserts in the last leaf, or if the tree is full from the right, it adds another layer on top of it (the old root will be the first of the new one).
// * `Prepend` is done similarly, but an offset is needed, because adding a new top node (where the current root would be the last node of the new root)
// * shifts the indices by half of the current tree's full size. The `offset` shifts them back to the correct index.
// * `Slice` is done by trimming the path from the root and discarding any `leading`/`trailing` values in effectively constant time (without memory leak, as in `Java`/`Clojure`).
// *
// * @author Pap Lőrinc
// */
//internal class BitMappedTrie<T> private constructor(
//    type: ArrayType<T>,
//    array: Any?,
//    offset: Int,
//    length: Int,
//    depthShift: Int,
//){
//    val type: ArrayType<T>
//
//    // Conditionally serializable
//    private val array: Any?
//    private val offset: Int
//    private val length: Int
//    private val depthShift: Int
//
//    init {
//        this.type = type
//        this.array = array
//        this.offset = offset
//        this.length = length
//        this.depthShift = depthShift
//    }
//
//    private fun boxed(): BitMappedTrie<T?>? {
//        return map<U?>(identity())
//    }
//
//    fun prependAll(iterable: Iterable<out T?>?): BitMappedTrie<T?> {
//        val iter: Collections.IterableWithSize<out T?> = withSize(iterable)
//        try {
//            return prepend(iter.reverseIterator(), iter.size())
//        } catch (ignored: java.lang.ClassCastException) {
//            return boxed()!!.prepend(iter.reverseIterator(), iter.size())
//        }
//    }
//
//    private fun prepend(iterator: MutableIterator<out T?>, size: Int): BitMappedTrie<T?> {
//        var size = size
//        var result: BitMappedTrie<T?> = this
//        while (size > 0) {
//            var array = result.array
//            var shift = result.depthShift
//            var offset = result.offset
//            if (result.isFullLeft) {
//                array = obj().copyUpdate(obj().empty(), BRANCHING_FACTOR - 1, array)
//                shift += BRANCHING_BASE
//                offset = treeSize(BRANCHING_FACTOR - 1, shift)
//            }
//
//            val index = offset - 1
//            val delta = min(size, lastDigit(index) + 1)
//            size -= delta
//
//            array = result.modify(array, shift, index, COPY_NODE, prependToLeaf(iterator))
//            result = BitMappedTrie<T?>(type, array, offset - delta, result.length + delta, shift)
//        }
//        return result
//    }
//
//    private val isFullLeft: Boolean
//        get() = offset == 0
//
//    private fun prependToLeaf(iterator: MutableIterator<out T?>): NodeModifier {
//        return NodeModifier { array: Any?, index: Int ->
//            var index = index
//            val copy: Any? = type.copy(array, BRANCHING_FACTOR)
//            while (iterator.hasNext() && index >= 0) {
//                type.setAt(copy, index--, iterator.next())
//            }
//            copy
//        }
//    }
//
//    fun appendAll(iterable: Iterable<out T?>?): BitMappedTrie<T?> {
//        val iter: Collections.IterableWithSize<out T?> = withSize(iterable)
//        try {
//            return append(iter.iterator(), iter.size())
//        } catch (ignored: java.lang.ClassCastException) {
//            return boxed()!!.append(iter.iterator(), iter.size())
//        }
//    }
//
//    private fun append(iterator: MutableIterator<out T?>, size: Int): BitMappedTrie<T?> {
//        var size = size
//        var result: BitMappedTrie<T?> = this
//        while (size > 0) {
//            var array = result.array
//            var shift = result.depthShift
//            if (result.isFullRight) {
//                array = obj().asArray(array)
//                shift += BRANCHING_BASE
//            }
//
//            val index = offset + result.length
//            val leafSpace = lastDigit(index)
//            val delta = min(size, BRANCHING_FACTOR - leafSpace)
//            size -= delta
//
//            array = result.modify(array, shift, index, COPY_NODE, appendToLeaf(iterator, leafSpace + delta))
//            result = BitMappedTrie<T?>(type, array, offset, result.length + delta, shift)
//        }
//        return result
//    }
//
//    private val isFullRight: Boolean
//        get() = (offset + length + 1) > treeSize(BRANCHING_FACTOR, depthShift)
//
//    private fun appendToLeaf(iterator: MutableIterator<out T?>, leafSize: Int): NodeModifier {
//        return NodeModifier { array: Any?, index: Int ->
//            var index = index
//            val copy: Any? = type.copy(array, leafSize)
//            while (iterator.hasNext() && index < leafSize) {
//                type.setAt(copy, index++, iterator.next())
//            }
//            copy
//        }
//    }
//
//    fun update(index: Int, element: T?): BitMappedTrie<T?> {
//        try {
//            val root = modify(array, depthShift, offset + index, COPY_NODE, updateLeafWith(type, element))
//            return BitMappedTrie<T?>(type, root, offset, length, depthShift)
//        } catch (ignored: java.lang.ClassCastException) {
//            return boxed()!!.update(index, element)
//        }
//    }
//
//    private fun updateLeafWith(type: ArrayType<T?>, element: T?): NodeModifier {
//        return NodeModifier { a: Any?, i: Int -> type.copyUpdate(a, i, element) }
//    }
//
//    fun drop(n: Int): BitMappedTrie<T?>? {
//        if (n <= 0) {
//            return this
//        } else if (n >= length) {
//            return empty<T?>()
//        } else {
//            val index = offset + n
//            val root = if (arePointingToSameLeaf(0, n))
//                array
//            else
//                modify(array, depthShift, index, obj()::copyDrop, IDENTITY)
//            return collapsed<T?>(type, root, index, length - n, depthShift)
//        }
//    }
//
//    fun take(n: Int): BitMappedTrie<T?>? {
//        if (n >= length) {
//            return this
//        } else if (n <= 0) {
//            return empty<T?>()
//        } else {
//            val index = n - 1
//            val root = if (arePointingToSameLeaf(index, length - 1))
//                array
//            else
//                modify(array, depthShift, offset + index, obj()::copyTake, IDENTITY)
//            return collapsed<T?>(type, root, offset, n, depthShift)
//        }
//    }
//
//    private fun arePointingToSameLeaf(i: Int, j: Int): Boolean {
//        return firstDigit(offset + i, BRANCHING_BASE) == firstDigit(offset + j, BRANCHING_BASE)
//    }
//
//    /* descend the tree from root to leaf, applying the given modifications along the way, returning the new root */
//    private fun modify(root: Any?, depthShift: Int, index: Int, node: NodeModifier, leaf: NodeModifier): Any? {
//        return if (depthShift == 0)
//            leaf.apply(root, index)
//        else
//            modifyNonLeaf(root, depthShift, index, node, leaf)
//    }
//
//    private fun modifyNonLeaf(root: Any?, depthShift: Int, index: Int, node: NodeModifier, leaf: NodeModifier): Any? {
//        var root = root
//        var previousIndex = firstDigit(index, depthShift)
//        root = node.apply(root, previousIndex)
//
//        var array = root
//        var shift = depthShift - BRANCHING_BASE
//        while (shift >= BRANCHING_BASE) {
//            val prev = previousIndex
//            previousIndex = digit(index, shift)
//            array = setNewNode(node, prev, array, previousIndex)
//            shift -= BRANCHING_BASE
//        }
//
//        val newLeaf = leaf.apply(obj().getAt(array, previousIndex), lastDigit(index))
//        obj().setAt(array, previousIndex, newLeaf)
//        return root
//    }
//
//    private fun setNewNode(node: NodeModifier, previousIndex: Int, array: Any?, offset: Int): Any? {
//        val previous: Any? = obj().getAt(array, previousIndex)
//        val newNode = node.apply(previous, offset)
//        obj().setAt(array, previousIndex, newNode)
//        return newNode
//    }
//
//    fun get(index: Int): T? {
//        val leaf = getLeaf(index)
//        val leafIndex = lastDigit(offset + index)
//        return type.getAt(leaf, leafIndex)
//    }
//
//    /**
//     * fetch the leaf, corresponding to the given index.
//     * Node: the offset and length should be taken into consideration as there may be leading and trailing garbage.
//     * Also, the returned array is mutable, but should not be mutated!
//     */
//    fun getLeaf(index: Int): Any? {
//        if (depthShift == 0) {
//            return array
//        } else {
//            return getLeafGeneral(index)
//        }
//    }
//
//    private fun getLeafGeneral(index: Int): Any? {
//        var index = index
//        index += offset
//        var leaf: Any? = obj().getAt(array, firstDigit(index, depthShift))
//        var shift = depthShift - BRANCHING_BASE
//        while (shift > 0) {
//            leaf = obj().getAt(leaf, digit(index, shift))
//            shift -= BRANCHING_BASE
//        }
//        return leaf
//    }
//
//    fun iterator(): Iterator<T> {
//        return object : Iterator<T> {
//            private val globalLength = this@BitMappedTrie.length
//            private var globalIndex = 0
//
//            private var index = lastDigit(offset)
//            private var leaf = getLeaf(globalIndex)
//            private var length: Int = type.lengthOf(leaf)
//
//            public override fun hasNext(): Boolean {
//                return globalIndex < globalLength
//            }
//
//            public override fun next(): T? {
//                if (!hasNext()) {
//                    throw NoSuchElementException("next() on empty iterator")
//                }
//
//                if (index == length) {
//                    setCurrentArray()
//                }
//                val next: T? = type.getAt(leaf, index)
//
//                index++
//                globalIndex++
//
//                return next
//            }
//
//            fun setCurrentArray() {
//                index = 0
//                leaf = getLeaf(globalIndex)
//                length = type.lengthOf(leaf)
//            }
//        }
//    }
//
//    fun <T2> visit(visitor: LeafVisitor<T2?>): Int {
//        var globalIndex = 0
//        var start = lastDigit(offset)
//        var index = 0
//        while (index < length) {
//            val leaf = getLeaf(index) as T2?
//            val end = getMin(start, index, leaf)
//
//            globalIndex = visitor.visit(globalIndex, leaf, start, end)
//
//            index += end - start
//            start = 0
//        }
//        return globalIndex
//    }
//
//    private fun getMin(start: Int, index: Int, leaf: Any?): Int {
//        return java.lang.Math.min(type.lengthOf(leaf), start + length - index)
//    }
//
//    fun filter(predicate: Predicate<in T?>): BitMappedTrie<T?>? {
//        val results: Any? = type.newInstance(length())
//        val length = this.visit<T?>(LeafVisitor { index: Int, leaf: T?, start: Int, end: Int ->
//            filter(
//                predicate,
//                results,
//                index,
//                leaf,
//                start,
//                end
//            )
//        })
//        return if (this.length == length)
//            this
//        else
//            ofAll<T?>(type.copyRange(results, 0, length))
//    }
//
//    private fun filter(predicate: Predicate<in T?>, results: Any?, index: Int, leaf: T?, start: Int, end: Int): Int {
//        var index = index
//        for (i in start..<end) {
//            val value: T? = type.getAt(leaf, i)
//            if (predicate.test(value)) {
//                type.setAt(results, index++, value)
//            }
//        }
//        return index
//    }
//
//    fun <U> map(mapper: Function<in T?, out U?>): BitMappedTrie<U?>? {
//        val results: Any? = obj().newInstance(length)
//        this.visit<T?>(LeafVisitor { index: Int, leaf: T?, start: Int, end: Int ->
//            map<Any?>(
//                mapper,
//                results,
//                index,
//                leaf,
//                start,
//                end
//            )
//        })
//        return ofAll<U?>(results)
//    }
//
//    private fun <U> map(
//        mapper: Function<in T?, out U?>,
//        results: Any?,
//        index: Int,
//        leaf: T?,
//        start: Int,
//        end: Int,
//    ): Int {
//        var index = index
//        for (i in start..<end) {
//            obj().setAt(results, index++, mapper.apply(type.getAt(leaf, i)))
//        }
//        return index
//    }
//
//    fun length(): Int {
//        return length
//    }
//
//    companion object {
//        const val BRANCHING_BASE: Int = 5
//        val BRANCHING_FACTOR: Int = 1 shl BRANCHING_BASE
//        val BRANCHING_MASK: Int = -1 ushr -BRANCHING_BASE
//
//        fun firstDigit(num: Int, depthShift: Int): Int {
//            return num shr depthShift
//        }
//
//        fun digit(num: Int, depthShift: Int): Int {
//            return lastDigit(firstDigit(num, depthShift))
//        }
//
//        fun lastDigit(num: Int): Int {
//            return num and BRANCHING_MASK
//        }
//
//        private const val serialVersionUID = 1L
//
//        private val EMPTY: BitMappedTrie<*> = BitMappedTrie<T?>(obj(), obj().empty(), 0, 0, 0)
//
//        fun <T> empty(): BitMappedTrie<T?>? {
//            return EMPTY as BitMappedTrie<T?>?
//        }
//
//        private fun treeSize(branchCount: Int, depthShift: Int): Int {
//            val fullBranchSize = 1 shl depthShift
//            return branchCount * fullBranchSize
//        }
//
//        fun <T> ofAll(array: Any?): BitMappedTrie<T?>? {
//            val type: ArrayType<T?> = ArrayType.of(array)
//            val size: Int = type.lengthOf(array)
//            return if (size == 0) empty<T?>() else ofAll<T?>(array, type, size)
//        }
//
//        private fun <T> ofAll(array: Any?, type: ArrayType<T?>, size: Int): BitMappedTrie<T?> {
//            var array = array
//            var shift = 0
//            var t: ArrayType<T?> = type
//            while (t.lengthOf(array) > BRANCHING_FACTOR) {
//                array = t.grouped(array, BRANCHING_FACTOR)
//                t = obj()
//                shift += BRANCHING_BASE
//            }
//            return BitMappedTrie<T?>(type, array, 0, size, shift)
//        }
//
//        /* drop root node while it has a single element */
//        private fun <T> collapsed(
//            type: ArrayType<T?>,
//            array: Any?,
//            offset: Int,
//            length: Int,
//            shift: Int,
//        ): BitMappedTrie<T?> {
//            var array = array
//            var offset = offset
//            var shift = shift
//            while (shift > 0) {
//                val skippedElements: Int = obj().lengthOf(array) - 1
//                if (skippedElements != digit(offset, shift)) {
//                    break
//                }
//                array = obj().getAt(array, skippedElements)
//                offset -= treeSize(skippedElements, shift)
//                shift -= BRANCHING_BASE
//            }
//            return BitMappedTrie<T?>(type, array, offset, length, shift)
//        }
//    }
//}
//
//internal fun interface NodeModifier {
//    fun apply(array: Any, index: Int): Any
//
//    companion object {
//        val COPY_NODE: NodeModifier = NodeModifier { o: Any, i: Int -> obj().copy(o, i + 1) }
//        val IDENTITY: NodeModifier = NodeModifier { o: Any, i: Int -> o }
//    }
//}
//
//internal fun interface LeafVisitor<T> {
//    fun visit(index: Int, leaf: T, start: Int, end: Int): Int
//}
